Factorization Machines (ICDM 2010)
概述
Steffen Rendle 于 ICDM 2010 发表的论文，提出用隐向量内积建模特征交互的通用预测模型，以线性复杂度解决稀疏数据下的特征交叉问题，成为 CTR 预估和推荐系统的基石模型。
关键内容
- 核心公式：FM 模型由三部分组成：全局偏置 $w_0$、一阶特征权重 $\sum w_i x_i$、二阶特征交互 $\sum_{i<j} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j$。通过将交互矩阵分解为隐向量内积，参数量从 $O(n^2)$ 降至 $O(kn)$。
- 线性复杂度推导：通过代数变换 $\sum_{i<j} \langle \mathbf{v}i, \mathbf{v}_j \rangle x_i x_j = \frac{1}{2} \sum{f=1}^{k} \left( (\sum_i v_{i,f} x_i)^2 - \sum_i v_{i,f}^2 x_i^2 \right)$，将计算复杂度从 $O(kn^2)$ 降至 $O(kn)$，稀疏数据下为 $O(k\bar{n})$。
- 稀疏数据有效性：与多项式 SVM 的独立交互参数不同，FM 的隐向量通过参数共享机制相互关联，即使特征 $i$ 和 $j$ 从未共现，只要 $\mathbf{v}_i$ 和 $\mathbf{v}_j$ 从其他交互中学到合理表示，FM 仍能预测其交互。
- 统一框架：FM 通过不同的特征编码方式可等价表示 矩阵分解（用户-物品 one-hot 编码）、SVD++（加入隐式反馈指示变量）、PITF（用户-物品-标签三元 one-hot）、FPMC 等专用分解模型，实现了"一个公式统一所有分解模型"。
- 训练方法：支持 SGD（大规模在线学习）、ALS（回归任务稳定）、MCMC（贝叶斯推断自动调参）三种优化方法，梯度可在线性时间内计算。
- 实验验证：在稀疏协同过滤数据上显著优于线性 SVM 和多项式核 SVM；在评分预测任务上与 MF 性能相当，加入丰富特征编码后可媲美 SVD++；在 Netflix 数据集（约1亿条评分）上展示工业级可扩展性。
- 局限性：仅支持二阶交叉（高阶 FM 因组合爆炸很少使用）；本质为线性模型，无法学习高度非线性模式；对所有特征对交叉等权处理，无法区分有意义交叉与噪声；隐向量维度 $k$ 的选择缺乏理论指导。
- 历史影响：直接催生 FFM（2016）、FNN（2016）、Wide & Deep（2016）、DeepFM（2017）、NFM（2017）、xDeepFM（2018）、AFM（2017）等一系列后续工作，是整个 CTR 预估模型谱系的"始祖"。美团、阿里巴巴、华为、Twitter 等公司在推荐和广告系统中大量使用 FM 及其变体。
- 与 Transformer 的结构相似性：FM 的交叉项 $\sum_i \sum_j \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j$ 与 Transformer 自注意力机制 $\text{softmax}(QK^T/\sqrt{d})V$ 存在结构相似性，都可看作通过"向量内积"衡量元素交互强度。
- Rendle 后续贡献：Rendle 加入 Google 后，于 2020 年发表 "Neural Collaborative Filtering vs. Matrix Factorization Revisited"，指出精心调优的 MF（FM 特例）在多项基准测试上仍可匹敌神经协同过滤模型。